package com.LeeCode;

import java.util.*;

/**
 * 逐层排序二叉树所需的最少操作数目
 */

public class Code2471 {
    public static void main(String[] args) {
        Integer[] arr = {1, 4, 3, 7, 6, 8, 5, null, null, null, null, 9, null, 10};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code2471().minimumOperations1(root));
    }

    public int minimumOperations(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        int ans = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int[] arr = new int[size], temp = new int[size];
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                arr[i] = temp[i] = cur.val;
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            Map<Integer, Integer> map = new HashMap<>();
            Arrays.sort(temp);
            for (int i = 0; i < arr.length; i++) map.put(temp[i], i);
            for (int i = 0; i < arr.length; i++) {
                while (arr[i] != temp[i]) {
                    int j = map.get(arr[i]);
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                    ans++;
                }
            }
        }
        return ans;
    }

    // 置换环
    public int minimumOperations1(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int n = queue.size();
            int[] a = new int[n];

            // 层序遍历填充当前层的节点
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                a[i] = node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // 离散化索引排序
            Integer[] id = new Integer[n];
            for (int i = 0; i < n; i++) {
                id[i] = i;
            }

            // 按照 a[id[i]] 排序
            Arrays.sort(id, (i, j) -> Integer.compare(a[i], a[j]));

            // 统计环的数量，每环最少交换次数为 (size - 1)
            boolean[] vis = new boolean[n];
            for (int v : id) {
                if (!vis[v]) {
                    int count = 0;
                    while (!vis[v]) {
                        count++;
                        vis[v] = true;
                        v = id[v];
                    }
                    ans += count - 1;
                }
            }
        }

        return ans;
    }
}
